/* 1. 代码随想录 */
/*
    1. 后序遍历的最后一个节点是当前子树的根；
    2. 在中序遍历中找到根的位置，左边是左子树，右边是右子树；
    3. 用中序的位置来计算出后序的左右子树范围；
    4. 递归进行构造，直到子 区间无效（start > end）；
*/


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 // step 1# 创建一个新节点
 struct TreeNode* createNode(int val) {
     struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
     node->val = val;
     node->left = NULL;
     node->right = NULL;
     return node;
 }
 
 // step 2# 递归构造函数，使用 inorder/postorder 的起始下标和长度来避免切片
 struct TreeNode* build(int* inorder, int inStart, int inEnd,
                        int* postorder, int postStart, int postEnd) {
     if (postStart > postEnd || inStart > inEnd) return NULL;
 
     // step 2.1# 根节点值为后序遍历最后一个元素
     int rootVal = postorder[postEnd];
     struct TreeNode* root = createNode(rootVal);
 
     // step 2.2# 查找根节点在中序遍历中的位置
     int rootIndex = inStart;
     while (rootIndex <= inEnd && inorder[rootIndex] != rootVal) {
         rootIndex++;
     }
 
     int leftSize = rootIndex - inStart;  // 左子树长度
 
     // step 2.3# 递归构造左右子树
     root->left = build(inorder, inStart, rootIndex - 1,
                        postorder, postStart, postStart + leftSize - 1);
 
     root->right = build(inorder, rootIndex + 1, inEnd,
                         postorder, postStart + leftSize, postEnd - 1);
 
     return root;
 }
 
 // step 3# 主接口函数：LeetCode 会调用这个函数
 struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
     if (inorderSize == 0 || postorderSize == 0) return NULL;
     return build(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1);
 }
 
 /* 2. 20250415 */
 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/*
    1. 找后序遍历的最后一个元素作为根节点
    2. 在中序遍历中找到该根节点的位置，以划分左右子树
    3. 计算左子树的大小，用于划分后序遍历中的左右部分
    4. 分别递归构造左子树和右子树
    5. 如果区间非法（越界），返回 NULL
*/

typedef struct TreeNode TreeNode;

// step 1# 创建一个新节点，分配内存并初始化值
TreeNode *createNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));  // 申请内存
    node->val = val;                                        // 设置节点值
    node->left = NULL;                                      // 初始化左右子树为空
    node->right = NULL;
    return node;
}

// step 2# 递归构建二叉树
TreeNode *build(int *in, int inStart, int inEnd,
                int *pos, int posStart, int posEnd) {
    // step 2.1# 如果当前区间非法，返回 NULL
    if (inStart > inEnd || posStart > posEnd) return NULL;

    // step 2.2# 后序遍历的最后一个元素为当前子树的根节点
    int val = pos[posEnd];
    TreeNode *curNode = createNode(val);

    // step 2.3# 在中序遍历中查找根节点位置
    int startIndex = inStart;
    while (startIndex <= inEnd && in[startIndex] != val) {
        startIndex++;
    }

    // step 2.4# 划分左子树的中序区间
    int nextInStartLeft = inStart;
    int nextInEndLeft = startIndex - 1;
    int leftSize = nextInEndLeft - nextInStartLeft + 1; // 左子树的节点数量

    // step 2.5# 划分左子树的后序区间
    int nextPosStartLeft = posStart;
    int nextPosEndLeft = posStart + leftSize - 1;

    // step 2.6# 划分右子树的中序区间
    int nextInStartRight = startIndex + 1;
    int nextInEndRight = inEnd;

    // step 2.7# 划分右子树的后序区间
    int nextPosStartRight = posStart + leftSize;
    int nextPosEndRight = posEnd - 1;  // 排除最后一个根节点

    // step 2.8# 递归构建左子树和右子树
    curNode->left = build(in, nextInStartLeft, nextInEndLeft,
                          pos, nextPosStartLeft, nextPosEndLeft);
    curNode->right = build(in, nextInStartRight, nextInEndRight,
                           pos, nextPosStartRight, nextPosEndRight);

    return curNode;
}

// step 3# 主函数接口，提供中序和后序遍历数组及其长度，返回构建后的根节点
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    TreeNode *root = build(inorder, 0, inorderSize - 1,
                           postorder, 0, postorderSize - 1);
    return root;
}
